package com.mdnote.structure.linked_list;

/**
 * @author Rhythm-2019
 * @date 2020/8/11
 * @description 环形链表，约瑟夫问题
 */
public class RangeLinkList{

    private static class Node {
        private int val;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    // 指向第一个节点
    private Node first;

    // 指向first的上一个元素
    private Node helper;

    public RangeLinkList() {
    }

    // 初始化
    public void init(int nums) {
        // 不合法
        if (nums < 1) {
            System.out.println("不能小于一个元素");
            return;
        }

        for (int i = 0; i < nums; i++) {
            // 只有一个元素
            if (i == 0) {
                // 创建新的对象
                this.first = new Node(i);
                // 让first自己指向自己
                this.first.next = this.first;
                this.helper = this.first;
            } else {
                // 创建下一个元素
                this.helper.next = new Node(i);
                // 让下一个元素指回first
                this.helper.next.next = first;
                // 进入下一步
                this.helper = this.helper.next;
            }
        }
    }

    public void show() {
        if (first.next == first) {
            System.out.println(first.val);
        } else {
            this.helper = first;
            while (true) {
                System.out.println(helper.val + "  ");
                if (first == helper.next) {
                    break;
                }
                this.helper = this.helper.next;
            }
        }
    }

    public void count(int startNo, int countNo, int nums) {
        // 先让helper走到first后面
        this.helper = first.next;
        while (helper.next != first) {
            this.helper = this.helper.next;
        }
        // 让first和helper同时走startNo步
        for (int i = 0; i < startNo; i++) {
            this.first = this.first.next;
            this.helper = this.helper.next;
        }

        // 数数
        while (true) {
            // Terminate
            if (helper == first) {
                System.out.println(first.val + "被弹出");
                break;
            }
            // 往后走K步 first指向的就是要出来的元素
            for (int i = 0; i < countNo; i++) {
                this.first = this.first.next;
                this.helper = this.helper.next;
            }

            System.out.println(first.val + "被弹出");
            helper.next = first.next;
            first = first.next;
        }

    }
}
